MINVO Basis: Finding simplexes with minimum volume enclosing polynomial curves

J. Tordesillas Torres, J.P. How

Computer-Aided Design Vol. 151, pp. 103341-1 - 103341-22

Summary:

This paper studies the polynomial basis that generates the smallest n-simplex enclosing a given n^th-degree polynomial curve in Rⁿ. Although the Bernstein and B-Spline polynomial bases provide feasible solutions to this problem, the simplexes obtained by these bases are not the smallest possible, which leads to overly conservative results in many CAD (computer-aided design) applications. We first prove that the polynomial basis that solves this problem (MINVO basis) also solves for the n^th-degree polynomial curve with largest convex hull enclosed in a given n-simplex. Then, we present a formulation that is independent of the n-simplex or n^th-degree polynomial curve given. By using Sum-Of-Squares (SOS) programming, branch and bound, and moment relaxations, we obtain high-quality feasible solutions for any n∈N, and prove (numerical) global optimality for n=1,2,3 and (numerical) local optimality for n=4. The results obtained for n=3 show that, for any given 3^rd-degree polynomial curve in R³, the MINVO basis is able to obtain an enclosing simplex whose volume is 2.36 and 254.9 times smaller than the ones obtained by the Bernstein and B-Spline bases, respectively. When n=7, these ratios increase to 902.7 and 2.997⋅10²¹, respectively.

Keywords: Minimum enclosing simplex; Curve with largest convex hull; Polynomial basis; Polynomial curve; Spline

JCR Impact Factor and WoS quartile: 4,300 - Q1 (2022); 3,000 - Q2 (2023)

DOI reference: https://doi.org/10.1016/j.cad.2022.103341

Published on paper: October 2022.

Published on-line: June 2022.

Citation:
J. Tordesillas Torres, J.P. How, MINVO Basis: Finding simplexes with minimum volume enclosing polynomial curves. Computer-Aided Design. Vol. 151, pp. 103341-1 - 103341-22, October 2022. [Online: June 2022]